package com.practice.niuke.new_direct_practice.class28;

/**
 * 给定一个非负整数 N，返回 N!结果的末尾为 0 的数量。
 * 例如:3!=6，结果的末尾没有 0，则返回 0。5!=120，结果的末尾有 1 个 0，返回 1。
 * 1000000000!，结果的末尾有 249999998 个 0，返回 249999998。
 * 补充问题：
 * 给定一个非负整数 N，如果用二进制数表达 N!的结果，返回最低位的 1 在哪个 位置
 * 上，认为最右的位置为位置 0。
 * 例如:1!=1，最低位的 1 在 0 位置上。2!=2，最低位的 1 在 1 位置上。1000000000!，
 * 最低位的 1 在 999999987 位置上。
 */
public class Code03_FactorialProblem {

	public static int zeroNum1(int num) {
		if (num < 0) {
			return 0;
		}
		int res = 0;
		int cur = 0;
		for (int i = 5; i < num + 1; i = i + 5) {
			cur = i;
			while (cur % 5 == 0) {
				res++;
				cur /= 5;
			}
		}
		return res;
	}

	public static int zeroNum2(int num) {
		if (num < 0) {
			return 0;
		}
		int res = 0;
		while (num != 0) {
			res += num / 5;
			num /= 5;
		}
		return res;
	}

	public static int rightOne1(int num) {
		if (num < 1) {
			return -1;
		}
		int res = 0;
		while (num != 0) {
			num >>>= 1;
			res += num;
		}
		return res;
	}

	public static int rightOne2(int num) {
		if (num < 1) {
			return -1;
		}
		int ones = 0;
		int rightOne = 0;
		while (num != 0) {
			rightOne = (num & (~num + 1));
			num -= rightOne;
			ones++;
		}
		return num - ones;
	}

	public static void main(String[] args) {
		int num = 1000000000;

		System.out.println(zeroNum2(num));
		System.out.println(zeroNum1(num));

		System.out.println(rightOne2(num));
		System.out.println(rightOne1(num));

	}

}
